{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #开幕式焰火"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numColor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #开幕式焰火"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。\n",
    "给定一棵二叉树 `root` 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`root = [1,3,2,1,null,2]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：焰火中有 3 个不同的颜色，值分别为 1、2、3\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`root = [3,3,3]`\n",
    ">\n",
    ">输出：`1`\n",
    ">\n",
    ">解释：焰火中仅出现 1 个颜色，值为 3\n",
    "\n",
    "**提示：**\n",
    "- `1 <= 节点个数 <= 1000`\n",
    "- `1 <= Node.val <= 1000`\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sZ59z6](https://leetcode.cn/problems/sZ59z6/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sZ59z6](https://leetcode.cn/problems/sZ59z6/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,1,null,2]', '[3,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        nums = []\n",
    "        def traversal(root) -> None:\n",
    "            if root is None:\n",
    "                return\n",
    "            else:\n",
    "                if root.val not in nums:\n",
    "                    nums.append(root.val)\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        traversal(root)\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        # 计算巨型烟火有多少种不同的颜色\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.val not in res:\n",
    "                res.append(root.val)\n",
    "            recur(root.left)\n",
    "            recur(root.right)\n",
    "        \n",
    "        res = []\n",
    "        recur(root)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res = set([])\n",
    "\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            \n",
    "            res.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        s = set()\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            s.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        st = set()\n",
    "        def dfs(u: TreeNode):\n",
    "            st.add(u.val)\n",
    "            if u.left: dfs(u.left)\n",
    "            if u.right: dfs(u.right)\n",
    "        dfs(root)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color = set()\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            color.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(color)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color = set()\n",
    "        que = deque([root])\n",
    "        \n",
    "        while len(que):\n",
    "            node = que.popleft()\n",
    "            color.add(node.val)\n",
    "            left = node.left\n",
    "            right = node.right\n",
    "            for _ in [left, right]:\n",
    "                if _:\n",
    "                    que.append(_)\n",
    "\n",
    "        return len(color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "\n",
    "        result = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            result.add(root.val)\n",
    "            if root.left:\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        a = set()\n",
    "        def dps(root):\n",
    "            if not root:\n",
    "                return\n",
    "            else:\n",
    "                a.add(root.val)\n",
    "                dps(root.left)\n",
    "                dps(root.right)\n",
    "        dps(root)\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        self.res = set()\n",
    "        self.traverse(root)\n",
    "        return len(self.res)\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.res.add(root.val)\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        # 前序遍历\n",
    "        ans = set()\n",
    "        def counter(node):\n",
    "            if node:\n",
    "                ans.add(node.val)\n",
    "                counter(node.left)\n",
    "                counter(node.right)\n",
    "        counter(root)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.st=set()\n",
    "\n",
    "    def dfs(self,root):\n",
    "        if root:\n",
    "            self.st.add(root.val)\n",
    "            self.dfs(root.left)\n",
    "            self.dfs(root.right)\n",
    "\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        self.dfs(root)\n",
    "        return len(self.st)\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color = set()\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            color.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(color)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        s=set()\n",
    "        que=[root]\n",
    "        while que:\n",
    "            q=que.pop()\n",
    "            s.add(q.val)\n",
    "            if q.left:\n",
    "                que.append(q.left)\n",
    "            if q.right:\n",
    "                que.append(q.right)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        s = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            s.add(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        def dfs(cur,res1):\n",
    "            if not cur:\n",
    "                return      \n",
    "            # 前序递归\n",
    "            res1.append(cur.val)\n",
    "            dfs(cur.left,res1)\n",
    "            dfs(cur.right,res1) \n",
    "            # # 中序递归\n",
    "            # dfs(cur.left)\n",
    "            # res.append(cur.val)\n",
    "            # dfs(cur.right)\n",
    "            # # 后序递归\n",
    "            # dfs(cur.left)\n",
    "            # dfs(cur.right)\n",
    "            # res.append(cur.val)      \n",
    "        res = []\n",
    "        dfs(root,res)\n",
    "        return len(set(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        return len(set(self.preorder(root)))\n",
    "\n",
    "    def preorder(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        traversal = [root.val]\n",
    "        if root.left is not None:\n",
    "            traversal.extend(self.preorder(root.left))\n",
    "        if root.right is not None:\n",
    "            traversal.extend(self.preorder(root.right))\n",
    "        return traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        def traversal(root: TreeNode):\n",
    "            if not root:\n",
    "                return None\n",
    "            self.res.append(root.val)\n",
    "            traversal(root.left)\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "\n",
    "        # print(self.res)\n",
    "        set_ = set(self.res)\n",
    "        return len(set_)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color = []\n",
    "        tree = [root]\n",
    "        while tree:\n",
    "            node = tree.pop(0)\n",
    "            color.append(node.val)\n",
    "            if node.left:\n",
    "                tree.append(node.left)\n",
    "            if node.right:\n",
    "                tree.append(node.right)\n",
    "        return len(set(color))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            _list = []\n",
    "            for x in stack:\n",
    "                if x.val not in color:\n",
    "                    color.append(x.val)\n",
    "                if x.left != None:\n",
    "                    _list.append(x.left)\n",
    "                if x.right != None:\n",
    "                    _list.append(x.right)\n",
    "            stack[:] = _list[:]\n",
    "        return len(color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        def Color(root:TreeNode):\n",
    "            if not root:\n",
    "                return\n",
    "            lis[root.val] = 1\n",
    "            Color(root.left)\n",
    "            Color(root.right)\n",
    "        lis = []\n",
    "        for i in range(1002):\n",
    "            lis.append(0)\n",
    "        Color(root)\n",
    "        sum = 0\n",
    "        for i in lis:\n",
    "            sum += i\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        ans, stack = set(), [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            ans.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        ans = []\n",
    "\n",
    "        def dfs(self,child: TreeNode) -> int:\n",
    "            if child == None:\n",
    "                return \n",
    "            if not child.val in ans:\n",
    "                ans.append(child.val)\n",
    "            dfs(self,child.left)\n",
    "            dfs(self,child.right)\n",
    "        dfs(self,root)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        ans = []\n",
    "        def helper(node: TreeNode):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            ans.append(node.val)\n",
    "            helper(node.left)\n",
    "            helper(node.right)\n",
    "            return\n",
    "        helper(root)\n",
    "        return len(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        self.lst = []\n",
    "        def dg(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.val not in self.lst:\n",
    "                self.lst.append(root.val)\n",
    "            dg(root.left)\n",
    "            dg(root.right)\n",
    "            return len(self.lst)\n",
    "        return dg(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        a = set()\n",
    "        def preorder(node):\n",
    "            if not node: return\n",
    "            a.add(node.val)\n",
    "            preorder(node.left)\n",
    "            preorder(node.right)\n",
    "        preorder(root)\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        cnt = set()\n",
    "        def bfs(s, node):\n",
    "            if node:\n",
    "                bfs(s, node.left)\n",
    "                cnt.add(node.val)\n",
    "                bfs(s, node.right)\n",
    "        \n",
    "        bfs(cnt, root)\n",
    "        return len(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        s = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            nonlocal s\n",
    "            s.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        self.color = set()\n",
    "\n",
    "        def travel(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            self.color.add(node.val)\n",
    "            travel(node.left)\n",
    "            travel(node.right)\n",
    "\n",
    "        travel(root)\n",
    "        return len(self.color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        ans = []\n",
    "        def helper(node: TreeNode):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val not in ans:\n",
    "                ans.append(node.val)\n",
    "            helper(node.left)\n",
    "            helper(node.right)\n",
    "            return\n",
    "        helper(root)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def preOrder(self, root:TreeNode, l: set):\n",
    "        if root is None:\n",
    "            return\n",
    "        l.add(root.val)\n",
    "        self.preOrder(root.left, l)\n",
    "        self.preOrder(root.right, l)\n",
    "        \n",
    "    def numColor(self, root:TreeNode) -> int:\n",
    "        ans = set()\n",
    "        self.preOrder(root,ans)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res = []\n",
    "        self.dbs(root, res)\n",
    "        l = []\n",
    "        for ele in res:\n",
    "            if ele not in l:\n",
    "                l.append(ele)\n",
    "        return len(l)\n",
    "    \n",
    "    def dbs(self, root, res):\n",
    "        if not root:\n",
    "            return\n",
    "        else:\n",
    "            res.append(root.val)\n",
    "            self.dbs(root.left, res)\n",
    "            self.dbs(root.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        valueList = []\n",
    "        def search(valueL,node):\n",
    "            if node:\n",
    "                search(valueL,node.left)\n",
    "                valueL.append(node.val)\n",
    "                search(valueL,node.right)\n",
    "        search(valueList,root)\n",
    "        return len(set(valueList))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        l = []\n",
    "        def child(root):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.val not in l:\n",
    "                l.append(root.val)\n",
    "            child(root.left)\n",
    "            child(root.right)\n",
    "        child(root)\n",
    "        return len(l)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                res.add(root.val)\n",
    "                dfs(root.left)\n",
    "                dfs(root.right)\n",
    "        res = set()\n",
    "        dfs(root)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        self.ans = {}\n",
    "        def dfs(root):\n",
    "            if not root: return \n",
    "            if root.val not in self.ans:\n",
    "                self.ans[root.val] = 1\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(self.ans.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color=set()\n",
    "        # 把二叉树的值遍历加到集合里，取长度，就是不重复的值\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root:\n",
    "                dfs(root.left)\n",
    "                color.add(root.val)\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        c = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            c.add(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            _list = []\n",
    "            for x in stack:\n",
    "                if x.val not in color:\n",
    "                    color.append(x.val)\n",
    "                if x.left != None:\n",
    "                    _list.append(x.left)\n",
    "                if x.right != None:\n",
    "                    _list.append(x.right)\n",
    "            stack[:] = _list[:]\n",
    "        return len(color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.cnt = 0\n",
    "\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        def traversal(root: TreeNode):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.val not in self.res:\n",
    "                self.res.append(root.val)\n",
    "            traversal(root.left)\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "\n",
    "        # print(self.res)\n",
    "        # set_ = set(self.res)\n",
    "        return len(self.res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        hax = set()\n",
    "        def bfs(li, node):\n",
    "            if node:\n",
    "                bfs(li, node.left)\n",
    "                hax.add(node.val)\n",
    "                bfs(li,node.right)\n",
    "        bfs(hax,root)\n",
    "        return len(hax)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        a=set()\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            new=[]\n",
    "            for i in stack:\n",
    "                a.add(i.val) \n",
    "                if i.left:\n",
    "                    new.append(i.left)\n",
    "                if i.right:\n",
    "                    new.append(i.right)\n",
    "            stack=new \n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        kk=set()\n",
    "        def bfs(li,node):\n",
    "            if node:\n",
    "                bfs(li,node.left)\n",
    "                kk.add(node.val)\n",
    "                bfs(li,node.right)\n",
    "        bfs(kk,root)\n",
    "        return len(kk)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        self.ans = set()\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            self.ans.add(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return len(self.ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        s=set()\n",
    "        que=[root]\n",
    "        while que:\n",
    "            q=que.pop(0)\n",
    "            s.add(q.val)\n",
    "            if q.left:\n",
    "                que.append(q.left)\n",
    "            if q.right:\n",
    "                que.append(q.right)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        kk=set()\n",
    "        def b(li, node):\n",
    "            if node:\n",
    "                b(li,node.left)\n",
    "                kk.add(node.val)\n",
    "                b(li,node.right)\n",
    "        b(kk,root)\n",
    "        return len(kk)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        self.ans = set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            self.ans.add(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(self.ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        \n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        def traversal(root: TreeNode):\n",
    "            if not root:\n",
    "                return None\n",
    "            self.res.append(root.val)\n",
    "            traversal(root.left)\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "\n",
    "        # print(self.res)\n",
    "        set_ = set(self.res)\n",
    "        return len(set_)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res = set()\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            res.add(node.val)\n",
    "        dfs(root)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color=set()\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root:\n",
    "                dfs(root.left)\n",
    "                color.add(root.val)\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        return len(color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "#利用stack获取所有元素\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.cnt = 0\n",
    "\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        def traversal(root: TreeNode):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.val not in self.res:\n",
    "                self.res.append(root.val)\n",
    "            traversal(root.left)\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "\n",
    "        # print(self.res)\n",
    "        # set_ = set(self.res)\n",
    "        return len(self.res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        color = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            _list = []\n",
    "            for x in stack:\n",
    "                if x.val not in color:\n",
    "                    color.append(x.val)\n",
    "                if x.left != None:\n",
    "                    _list.append(x.left)\n",
    "                if x.right != None:\n",
    "                    _list.append(x.right)\n",
    "            stack[:] = _list[:]\n",
    "        return len(color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def numColor(self, root: TreeNode) -> int:\n",
    "        res_set = set()\n",
    "        stack = [root,]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            res_set.add(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return len(res_set)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
